package com.ztr.leetcode100.sumoftwonumbers;


import java.util.Arrays;
import java.util.HashMap;

public class SumOfTwoNumbers {

    /**
     * 题目描述：
     *
     * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
     * 示例:
     * 给定 nums = [2, 7, 11, 15], target = 9
     * 因为 nums[0] + nums[1] = 2 + 7 = 9
     * 所以返回 [0, 1]
     */

    /**
     * 使用哈希表找出数组中两个数之和等于特定目标值的那两个数的索引。
     * 这个方法避免了二次遍历数组，通过哈希表的快速查找特性，将时间复杂度降低到O(n)。
     *
     * @param nums 整数数组，其中包含要查找的两个数。
     * @param target 目标值，我们需要找到两个数的和等于这个值。
     * @return 包含两个数索引的数组，如果不存在这样的两个数则返回null。
     */
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 检查当前数字是否已存在于哈希表中，如果是，则返回这两个数的索引。
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }
            // 将当前数字与目标值之差作为键，当前索引作为值存入哈希表。
            // 这样做是为了后续能够快速找到与当前数字配对的数。
            map.put(target - nums[i], i);
        }
        // 如果没有找到符合条件的两个数，返回null。
        return null;
    }

    /**
     * 主函数，程序的入口点。
     * @param args 命令行参数，本程序中未使用。
     */
    public static void main(String[] args) {
        /* 初始化一个整数数组，包含四个元素。 */
        int[] nums = {2, 7, 11, 15};
        /* 设定目标值，本示例中目标是找到两个数的和等于9。 */
        int target = 9;
        /* 调用twoSum函数，寻找数组中两个数的索引，使其和等于target。 */
        int[] ints = twoSum(nums, target);
        /* 输出找到的两个数的索引。 */
        System.out.println(Arrays.toString(ints));
    }


}
